The retrieval of data from databases using search inputs involves significant technical innovation. Many solutions to text-based searching and even image-based searching have been developed by companies such as Google™. In these cases, the search input for the text databases is text and the search input for Google™ Goggles™ are images.
However, one area of data search remains difficult to solve. This is the field of searching within databases comprising 3D data, in particular, databases comprising 3D models (shapes). It is further desirous to be able to retrieve from those databases 3D model results using a 3D model as a search input.
There exist several 3D model search systems, including VizSeek™, CADseek™, Shapespace™ and Princeton's 3D Model Search Engine. All of these methods attempt to normalize for orientation of the search input, either by re-orienting the model/image, or by making the shape signature rotation invariant.
For efficient matching, for each 3D model a “shape descriptor” (or “shape signature”) is computed: a relatively small set of data that can be efficiently compared, but still represents sufficient characteristics of the shape such that dissimilar shapes have dissimilar descriptors. For an extensive overview of previous work in 3D shape retrieval, further information can be found in “A survey of content based 3D shape retrieval methods”, by J. W. H. Tangelder and R. C. Veltkamp, 2007.
Because of the regular nature of CAD (Computer-Aided Design) models, previous work in CAD shape retrieval has focused on view-based methods: a 3D model is represented by a number of 2D views (projections). Individual 2D shape signatures are computed for these views, which are then compared as a set. The 2D signatures are usually based on a Fourier transformation of the image boundary (see, for example, the Ph.D. thesis “3D Model Retrieval” by D. V. Vranić, 2003 or “Visual Based 3D CAD Retrieval using Fourier Mellin Transform” by X. Li, 2008).
However, all current methods that use shape descriptors and 2D views remain ineffective for accurate matching. This is because those methods that use automated orientation normalisation have poor accuracy, and those that use rotation invariant methods result in sub-optimal matching due to the use of mechanisms such as the Fourier transform.
It is an object of the present invention to provide a system for 3D model database retrieval which overcomes the disadvantages of the prior art, or at least provides a useful alternative.